<?php
/**
 * @title 464. 我能赢吗 - 二进制
 * @author start2004
 */

// ini_set("memory_limit", "128M");

// class Solution {
//
//     function find() {
//
//     }
// }


class Solution {

    /**
     * @param Integer $maxChoosableInteger
     * @param Integer $desiredTotal
     * @return Boolean
     */
    function canIWin($maxChoosableInteger, $desiredTotal) {
        /**
         * @since 2020-09-21 是否有解, 所有值总和是否能达到目标值
         */
        $sum = ($maxChoosableInteger * ($maxChoosableInteger+1)) >> 1;
        if($sum < $desiredTotal){
            return false;
        } else {}

        /**
         * @since 2020-09-22 增加缓存
         */
        $this->dp = [];
        
        /**
         * @since 2020-09-22 计算先手是否必胜
         */
        $result = self::find(str_repeat("0", $maxChoosableInteger), $maxChoosableInteger, $desiredTotal);

        /**
         * @return
         */
        return $result;
    }

    /**
     * @title 计算胜负关系
     * @author start2004
     * @since 2020-09-22 Created
     *
     * @param string $nums
     * @param int $len
     * @param int $desiredTotal
     * @return boolean
     */
    public function find($nums = '', $len = 0, $desiredTotal = 0){
        /**
         * @since 2020-09-22 检查缓存
         */
        $dpKey = $nums ."-". $desiredTotal;
        if(isset($this->dp[$dpKey])){
            return $this->dp[$dpKey];
        } else {}

        /**
         * @since 2020-09-22 找到最大值, 检查是否直接达到目标值, 获胜
         */
        for($i=$len-1; $i>=0; $i--){
            if($nums[$i] == "0"){
                /**
                 * @since 2020-09-22 倒序第一个未使用的数字, 即最大值, 如果能达到目标值, 即获胜
                 */
                if($i+1 >= $desiredTotal){
                    $this->dp[$dpKey] = true;
                    return true;
                } else {
                    /**
                     * @since 2020-09-22 如果不大于, 尝试其他途径
                     */
                }
                break;
            } else {}
        }

        /**
         * @since 2020-09-22 各种情况尝试
         */
        for(; $i>=0; $i--){
            if($nums[$i] == 0){
                $nums[$i] = 1;

                /**
                 * @since 2020-09-22 后手输, 先手赢
                 */
                if(self::find($nums, $len, $desiredTotal-$i-1) === false){
                    $this->dp[$dpKey] = true;
                    return true;
                } else {
                    /**
                     * @since 2020-09-22 还原, 继续下次循环
                     */
                    $nums[$i] = 0;
                }
            } else {}
        }

        /**
         * @since 2020-09-22 未break返回, 说明所有情况均试过, 没有一种情况获胜
         * @return
         */
        $this->dp[$dpKey] = false;
        return false;
    }
}

/**
 * @url http://127.0.0.1/leetcode/202009/2020.09.21_5.php
 */
$datas = [
    [10, 11],
    [10, 12],
    [10, 13],
    [10, 14],
    [10, 15],
    [10, 16],
    [10, 17],
    [10, 18],
    [10, 19],
    [10, 20],
    [10, 21],
    [10, 22],
    [10, 23],
    [10, 24],
    [12, 60],
    [15, 70],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->canIWin(...$data);
    // $result = $obj->($xhprof->tree($data));
    // $result = $obj->find(...$data);
    var_dump($result);
    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat("<br>", 3);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $result = $obj->$data[0][$i](...$data[1][$i]);
//
//         echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
